Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
Input: root = [2,1,3] Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -231 <= Node.val <= 231 - 1
Average Rating: 4.33 (295 votes)
Video Solution
Solution Article
Tree definition
First of all, here is the definition of the TreeNode which we would use.
Intuition
On the first sight, the problem is trivial. Let's traverse the tree
and check at each step if node.right.val > node.val and
node.left.val < node.val. This approach would even work for some
trees
The problem is this approach will not work for all cases. Not only the right child should be larger than the node but all the elements in the right subtree. Here is an example :
That means one should keep both upper
and lower limits for each node while traversing the tree,
and compare the node value not
with children values but with these limits.
Approach 1: Recursive Traversal with Valid Range
The idea above could be implemented as a recursion. One compares the node value with its upper and lower limits if they are available. Then one repeats the same step recursively for left and right subtrees.
Complexity Analysis
- Time complexity : O(N) since we visit each node exactly once.
- Space complexity : O(N) since we keep up to the entire tree.
Approach 2: Iterative Traversal with Valid Range
The above recursion could be converted into iteration, with the help of an explicit stack. DFS would be better than BFS since it works faster here.
Complexity Analysis
- Time complexity : O(N) since we visit each node exactly once.
- Space complexity : O(N) since we keep up to the entire tree.
Approach 3: Recursive Inorder Traversal
Algorithm
Let's use the order of nodes in the
inorder traversal
Left -> Node -> Right.
Here the nodes are enumerated in the order you visit them,
and you could follow 1-2-3-4-5 to compare different strategies.
Left -> Node -> Right order of inorder traversal
means for BST that each element should be smaller
than the next one.
Hence the algorithm with O(N) time complexity and O(N) space complexity could be simple:
-
Compute inorder traversal list
inorder. -
Check if each element in
inorderis smaller than the next one.
Do we need to keep the whole
inordertraversal list?
Actually, no. The last added inorder element is enough to ensure at each step that the tree is BST (or not). Hence one could merge both steps into one and reduce the used space.
Code
We can implement the algorithm recursively.
Complexity Analysis
-
Time complexity : O(N) in the worst case when the tree is a BST or the "bad" element is a rightmost leaf.
-
Space complexity : O(N) for the space on the run-time stack.
Approach 4: Iterative Inorder Traversal
Alternatively, we could implement the above algorithm iteratively.
Complexity Analysis
-
Time complexity : O(N) in the worst case when the tree is BST or the "bad" element is a rightmost leaf.
-
Space complexity : O(N) to keep
stack.
Last Edit: December 13, 2018 10:19 AM
Other approach to solve this problem would be to use inorder traversal properties where previous element in output would always be lesser than the current output.
December 13, 2018 2:51 AM
Heaps definitely aren't "usually implemented as binary search trees." They're usually implemented as flat arrays.
March 14, 2019 9:36 PM
Share a concise solution, 5 lines
bool isValidBST(TreeNode* root, TreeNode* min=NULL, TreeNode* max=NULL) {
if (!root) return true;
if (min != NULL && root->val <= min->val) return false;
if (max != NULL && root->val >= max->val) return false;
return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);
}
January 13, 2019 5:39 AM
Just curisou, why BFS is slower than DFS?
February 23, 2019 4:42 PM
Something recursive here:
class Solution {
public boolean isValidBST(TreeNode root) {
return checkNode(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean checkNode(TreeNode node, long min, long max) {
if (node == null){
return true;
}
if(node.val > min && node.val < max){
return (checkNode(node.left, min, node.val) && checkNode(node.right, node.val, max));
} else {
return false;
}
}
}
January 23, 2019 10:15 AM
The iterative solution is unnecessarily complicated. You can leverage the fact that an in-order traversal for a BST yields a monotonically increasing sequence. Obviously, it's the same asymptotic complexity but the code is much shorter & easier to follow (IMHO):
bool isValidBST(TreeNode* root) {
if (root == nullptr) return true;
stack<TreeNode*> s;
TreeNode* current = root; TreeNode* prev = nullptr;
while (current || !s.empty())
{
while(current)
{
s.push(current);
current = current->left;
}
current = s.top(); s.pop();
if (prev && prev->val >= current->val) return false;
prev = current;
current = current->right;
}
return true;
}
Last Edit: February 10, 2019 8:14 AM
The Java code of the first recursive solution can be simplified.
class Solution {
private boolean isBSTHelper(TreeNode node, long lower_limit, long upper_limit) {
if (node == null) {
return true;
}
if (node.val <= lower_limit || upper_limit <= node.val) {
return false;
}
return isBSTHelper(node.left, lower_limit, node.val) && isBSTHelper(node.right, node.val, upper_limit);
}
public boolean isValidBST(TreeNode root) {
return isBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
}
Last Edit: April 3, 2021 10:28 PM
I think, In the first approach, space will be O(h).
My recursive solution:
Time complexity O(N)
Space complexity O(h)
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
return self.checkIfValid(root, -2**32, 2**32)
def checkIfValid(self, root, minRange, maxRange):
if not root:
return True
if minRange >= root.val or maxRange <= root.val:
return False
return self.checkIfValid(root.left, minRange, root.val) and self.checkIfValid(root.right, root.val, maxRange)
Last Edit: May 26, 2019 11:40 AM
Anyone know why double inorder = - Double.MAX_VALUE instead of int inorder = -Integer.MIN_VALUE
May 24, 2019 10:48 AM
Why in Approach 1: Recursion, the Space complexity is O(N)? I think no other auxiliary space is needed?
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/03/2021 19:49 | Accepted | 24 ms | 21.7 MB | cpp |
| 05/31/2021 20:24 | Accepted | 28 ms | 21.6 MB | cpp |
| 05/31/2021 20:23 | Wrong Answer | N/A | N/A | cpp |
| 05/31/2021 20:22 | Runtime Error | N/A | N/A | cpp |
| 04/28/2021 12:06 | Accepted | 8 ms | 21.5 MB | cpp |
| 06/18/2020 08:50 | Accepted | 20 ms | 21.5 MB | cpp |
| 06/05/2020 09:07 | Accepted | 20 ms | 21.5 MB | cpp |
| 06/05/2020 09:00 | Runtime Error | N/A | N/A | cpp |
xxxxxxxxxx/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: bool isValidBST(TreeNode* root) { return isValidHelp(root, NULL, NULL); } bool isValidHelp(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) { if(!root) return true; if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val) return false; return isValidHelp(root->left, minNode, root) && isValidHelp(root->right, root, maxNode); }};